﻿//class Solution
//{
//public:
//	vector<int> getLeastNumbers(vector<int>& nums, int k)
//	{
//		srand(time(NULL));
//		qsort(nums, 0, nums.size() - 1, k);
//		return { nums.begin(), nums.begin() + k };
//	}
//	void qsort(vector<int>& nums, int l, int r, int k)
//	{
//		if (l >= r) return;
//		// 1. 随机选择⼀个基准元素 + 数组分三块
//		int key = getRandom(nums, l, r);
//		int left = l - 1, right = r + 1, i = l;
//		while (i < right)
//		{
//			if (nums[i] < key) swap(nums[++left], nums[i++]);
//			else if (nums[i] == key) i++;
//			else swap(nums[--right], nums[i]);
//		}
//		// [l, left][left + 1, right - 1] [right, r]
//		// 2. 分情况讨论
//		int a = left - l + 1, b = right - left - 1;
//		if (a > k) qsort(nums, l, left, k);
//		else if (a + b >= k) return;
//		else qsort(nums, right, r, k - a - b);
//	}
//	int getRandom(vector<int>& nums, int l, int r)
//	{
//		return nums[rand() % (r - l + 1) + l];
//	}
//};


//class Solution
//{
//	vector<int> tmp;
//public:
//	vector<int> sortArray(vector<int>& nums)
//	{
//		tmp.resize(nums.size());
//		mergeSort(nums, 0, nums.size() - 1);
//			return nums;
//	}
//	void mergeSort(vector<int>& nums, int left, int right)
//	{
//		if (left >= right) return;
//		int mid = (left + right) >> 1;
//		// [left, mid] [mid + 1, right]
//		// 左右区间排序
//		mergeSort(nums, left, mid);
//		mergeSort(nums, mid + 1, right);
//		//合并两个有序数组
//		int cur1 = left, cur2 = mid + 1, i = 0;
//		while (cur1 <= mid && cur2 <= right)
//			tmp[i++] = nums[cur1] <= nums[cur2] ? nums[cur1++] : nums[cur2++]
//			// 处理没有遍历完的数组
//			while (cur1 <= mid) tmp[i++] = nums[cur1++];
//		while (cur2 <= right) tmp[i++] = nums[cur2++];
//		// 4. 还原
//		for (int i = left; i <= right; i++)
//			nums[i] = tmp[i - left];
//	}
//};

//
//class Solution
//{
//	int tmp[50010];
//public:
//	int reversePairs(vector<int>& nums)
//	{
//		return mergeSort(nums, 0, nums.size() - 1);
//	}
//	int mergeSort(vector<int>& nums, int left, int right)
//	{
//		if (left >= right) return 0;
//		int ret = 0;
//		// 1. 找中间点，将数组分成两部分
//		int mid = (left + right) >> 1;
//		// [left, mid][mid + 1, right]
//		// 2. 左边的个数 + 排序 + 右边的个数 + 排序
//		ret += mergeSort(nums, left, mid);
//		ret += mergeSort(nums, mid + 1, right);
//		// 3. ⼀左⼀右的个数
//		int cur1 = left, cur2 = mid + 1, i = 0;
//		while (cur1 <= mid && cur2 <= right) // 升序的时候
//		{
//			if (nums[cur1] <= nums[cur2])
//			{
//				tmp[i++] = nums[cur1++];
//			}
//			else
//			{
//				ret += mid - cur1 + 1;
//				tmp[i++] = nums[cur2++];
//			}
//		}
//		// 4. 处理⼀下排序
//		while (cur1 <= mid) tmp[i++] = nums[cur1++];
//		while (cur2 <= right) tmp[i++] = nums[cur2++];
//		for (int j = left; j <= right; j++)
//			nums[j] = tmp[j - left];
//
//		return ret;
//	}
//};


class Solution
{
	int tmp[50010];
public:
	int reversePairs(vector<int>& nums)
	{
		return mergeSort(nums, 0, nums.size() - 1);
	}
	int mergeSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return 0;
		int ret = 0;
		// 1. 找中间点，将数组分成两部分
		int mid = (left + right) >> 1;
		// [left, mid][mid + 1, right]
		// 2. 左边的个数 + 排序 + 右边的个数 + 排序
		ret += mergeSort(nums, left, mid);
		ret += mergeSort(nums, mid + 1, right);
		// 3. ⼀左⼀右的个数
		int cur1 = left, cur2 = mid + 1, i = 0;
		while (cur1 <= mid && cur2 <= right) // 降序的版本
		{
			if (nums[cur1] <= nums[cur2])
			{
				tmp[i++] = nums[cur2++];
			}
			else
			{
				ret += right - cur2 + 1;
				tmp[i++] = nums[cur1++];
			}
		}
		// 4. 处理⼀下排序
		while (cur1 <= mid) tmp[i++] = nums[cur1++];
		while (cur2 <= right) tmp[i++] = nums[cur2++];
		for (int j = left; j <= right; j++)
			nums[j] = tmp[j - left];

		return ret;
	}
};